<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      class Node {
        constructor(key) {
          this.key = key;
          this.left = null; // 左指针
          this.right = null; // 右指针
        }
      }
      // 用来标记计算结果
      const compare = {
        LESS_THAN: -1, // 小于
        BIGGER_THAN: 1, // 大于
        EQUALS: 0, // 等于
      };

      // 封装二叉树
      class BST {
        constructor() {
          // 根节点
          this.root = null;
        }

        // -----------------------------------------------------------------------------------------
        // 添加方法
        insert(value) {
          // 判断情况 根节点是否为空
          if (this.root == null) {
            this.root = new Node(value);
          } else {
            // 此时  需要使用递归  因为不知道二叉树的深度  所以需要一直去判断
            this.insertNode(this.root, value);
          }
        }

        // 单独封装一个方法 用来判断如果添加的value比原来的node小  那么添加到左节点 否则去右节点
        insertNode(node, value) {
          // 如果是小于的情况
          if (this.compareFn(value, node.key) === compare.LESS_THAN) {
            if (node.left == null) {
              // 到最后一层停止
              node.left = new Node(value);
            } else {
              // 一直递归调用
              this.insertNode(node.left, value);
            }
          } else {
            if (node.right == null) {
              node.right = new Node(value);
            } else {
              this.insertNode(node.right , value);
            }
          }
        }

        // 计算方法单独封装
        compareFn(a, b) {
          if (a === b) {
            return compare.EQUALS;
          }
          return a < b ? compare.LESS_THAN : compare.BIGGER_THAN;
        }

        // ----------------------------------------------------------------------------------------------------------

        // 中序遍历
        inOrderMap(callback) {
          this.inOrderMapNode(this.root, callback);
        }

        /* 
        真正的执行函数抽离出来
        核心思想: 先遍历所有左节点直到没有元素 那么此时就是最小的元素  再打印对应的上级节点 其次是右节点  来实现从小到大的排序 
        */
        inOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            // 先递归左节点
            this.inOrderMapNode(node.left, callback);
            callback(node.key);
            this.inOrderMapNode(node.right, callback);
          }
        }

        // 先序遍历
        preOrderMap(callback) {
          this.preOrderMapNode(this.root, callback);
        }

        preOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            // 先递归父节点
            callback(node.key);
            this.preOrderMapNode(node.left, callback);
            this.preOrderMapNode(node.right, callback);
          }
        }

        // 后序遍历
        pastOrderMap(callback) {
          this.pastOrderMapNode(this.root, callback);
        }
        pastOrderMapNode(node, callback) {
          // 终止递归 查不到元素
          if (node != null) {
            this.pastOrderMapNode(node.left, callback);
            this.pastOrderMapNode(node.right, callback);
            callback(node.key);
          }
        }

        // 找到最小值
        min() {
          return this.minNode(this.root);
        }
        minNode(node) {
          let current = node;
          // 终于循环的条件
          while (current != null && current.left != null) {
            current = current.left;
          }
          return current;
        }

        // 找到最大值
        max() {
          return this.maxNode(this.root);
        }
        maxNode(node) {
          let current = node;
          while (current != null && current.right != null) {
            current = current.right;
          }
          return current;
        }

        // 搜索是否存在
        search(key){
          return this.searchNode(this.root , key)
        }
        // 核心思想: 利用计算方法  如果小于 那么递归左分支到null停止  反之是右分支
        searchNode(node , key){
          // 如果一进入就找到null  说明已经到最后都没找到
          if(node === null){
            return false
          }
          if(this.compareFn(key , node.key) === compare.LESS_THAN){
            return this.searchNode(node.left , key)
          }else if (this.compareFn(key , node.key) === compare.BIGGER_THAN){
            return this.searchNode(node.right , key)
          }else {
            return true
          }
        }

        // 移除
        remove(key){
          this.root = this.removeNode(this.root , key)
        } 
        removeNode(node , key){
          /* 
          分情况来讨论
          */
          if(node == null){
            return null
          }
          // 如果传入的节点小于左节点 那么遍历左侧的节点  反之遍历右侧节点
          if(this.compareFn(key ,node.key) === compare.LESS_THAN){
            node.left = this.removeNode(node.left , key) // 每次执行 覆盖原节点
            return node
          }else if(this.compareFn(key ,node.key) === compare.BIGGER_THAN){
            node.right = this.removeNode(node.right , key)
            return node
          }else{
            // 这里是分类讨论的重点 
            // 已经找到要删除的节点  删除一个节点时 他的左侧 右侧 上级都会被修改 如何排列呢?

            // - 最简单的情况 最底层的节点 没有左节点和右节点
            if(node.left == null && node.right == null){
              node = null              
              return node
            }
            // - 当要删除的节点只有一个节点的时候 可能是左节点 也可能是右节点 直接让下一级节点上升到原来的位置
            if(node.left == null){
              node = node.right
              return node
            }else if(node.right == null){
              node = node.left
              return node
            }

            // - 最麻烦的情况  要删除的节点有两个子节点的时候
            // 先找到右侧最小的节点
            const target = this.minNode(node.right)
            node.key = target.key

            // 进行覆盖  在node.right里删除target这个元素
            node.right = this.removeNode(node.right, target.key)
            return node

          }

        }

      }

      const tree = new BST();

      tree.insert(100);
      tree.insert(90);
      tree.insert(88);
      tree.insert(98);
      tree.insert(108);
      tree.insert(106);
      tree.insert(110);


      // 测试遍历
      tree.inOrderMap((value) => {
        // console.log(value);
      });
      tree.preOrderMap((value) => {
        // console.log(value);
      });
      tree.pastOrderMap((value) => {
        // console.log(value);
      });
    </script>
  </body>
</html>
